{\rtf1\mac\ansicpg10000\cocoartf824\cocoasubrtf480
{\fonttbl\f0\fswiss\fcharset77 Helvetica;}
{\colortbl;\red255\green255\blue255;}
\margl1440\margr1440\vieww13000\viewh19600\viewkind0
\pard\tx720\tx1440\tx2160\tx2880\tx3600\tx4320\tx5040\tx5760\tx6480\tx7200\tx7920\tx8640\ql\qnatural\pardirnatural

\f0\fs24 \cf0 To use the vpi (Variable Precision Integer) arithmetic tools, you will need to have the top level directory (VariablePrecisionIntegers) on your MATLAB search path.\
\

\fs32 Do NOT put the @vpi directory on your search path!!! Do NOT take any functions from that directory, as this will break the operation of the vpi code!!!
\fs24 \
\
To see the usage of these functions, a lengthy set of demos has been provided. You can view them as html simply by opening the file demo_vpi.html into your web browser. In general, this toolbox contains every operation that I could implement on a scalar integer variable. Note that you can add, subtract, multiply, or divide two vpi numbers exactly as you would do in matlab, you can also do those same operations on a vpi number with any integer. You can even work with simple arrays of vpi numbers. For example, you can do things like this:\
\
>> a = vpi(2);\
>> b = 17*a^112 + 3;\
>> [a,b]*[b;a+1]\
\
These vpi tools are not truly infinite precision, in the sense that if you work with such large numbers that you run out of memory, they will still fail. This will be a really big number however, and any operations on something even close to that huge will be really slow to work with in MATLAB. But most operations on numbers with only a few hundred or even many thousands of digits will be quite acceptably fast.\
\
A list of the specific functions to be found in this toolbox is as follows:\
\
\
Creator tool for vpi objects\
vpi		- Creator function for a variable precision integer\
\
\
General mathematical operations on a vpi number\
abs		- Absolute value of a vpi object\
exp		- The integer part of exp(x)\
log		- Natural logarithm of the (positive) vpi number N\
log10		- Base 10 logarithm of the (positive) vpi number N\
log2		- Base 2 logarithm of the (positive) vpi number N\
minus		- Subtracts two vpi objects, or one vpi and a constant\
modroot	- Find x such that (mod(x^2,p) == a), the sqrt in modular arithmetic\
mpower	- raises a vpi object to a positive integer (numeric) power\
mrdivide	- Integer division for two vpi objects\
mtimes	- Multiplies two vpi objects, or a product of a numeric var to an vpi\
plus		- Adds two vpi objects, or adds a numeric var to an vpi\
power		- Raises a vpi object to a positive integer (numeric) power\
prod		- Product of elements\
rdivide	- Integer division for two vpi objects\
sign		- Extracts the sign of a vpi object\
sqrt		- Integer part of the square root of the (non-negative) vpi number N\
sum		- Sum of elements\
times		- Multiplies two vpi objects, or a product of a numeric var to an vpi\
uminus	- Negates a vpi object, -N\
uplus		- Unary plus for an vpi object, +N\
\
\
Extracting portions of (or information about) a vpi number to work with\
leadingdigit	- Extract the highest order digits of a vpi object\
order		- Power of 10 associated with the highest order digit of a vpi object\
sign		- Extracts the sign of a vpi object\
trailingdigit	- Extract the lowest order digits of a vpi object\
\
\
Relational operations, comparisons of vpi objects and/or numeric variables\
eq		- Test for equality between a pair of vpi objects\
find		- Locates non-zero elements of a vpi array\
ge		- Test for inequality (>=) between a pair of vpi objects\
gt		- Test for strict inequality (>) between a pair of vpi objects\
iseven	- Test to see if a vpi object represents an even number\
isunit		- Test to see if a vpi object is +1 or -1\
iszero		- Test to see if a vpi object is zero\
le		- Test for inequality (<=) between a pair of vpi objects\
lt		- Test for strict inequality (<) between a pair of vpi objects\
sort		- Sort a vpi array or vector\
\
\
Working with the factors of vpi numbers, generating those factors, and primality testing\
factor		- Computes the factors of an integer\
gcd		- Greatest Common Divisor of two (or more) vpi objects\
isprime	- use a specified primality test to check if a number is prime\
lcm		- Least Common Multiple of two (or more) vpi objects\
legendresymbol - computes the Legendre symbol (a/p)\
mersenne	- identify whether 2^p-1 is a Mersenne prime, using the Lucas-Lehmer test\
modroot	- Find x such that (mod(x^2,p) == a), the sqrt of a quadratic residue\
quadraticresidues - list all the quadratic residues of a number\
totient		- The number of positive integers less than N that are coprime to N\
\
\
Modulo arithmetic, integer division, quotient/remainder computations\
mod		- Modulus after integer division of vpi objects\
modrank	- Compute the rank of an integer array, modulo p\
minv		- The multiplicative inverse of a: x such that (mod(a*x,p == 1)\
powermod	- Compute mod(a^d,n)\
quotient	- Divides two vpi objects, computing a quotient and remainder\
rdivide	- Integer division for two vpi objects\
rem		- Remainder upon integer division of vpi objects\
\
\
Add/Multiply products of lists of numbers into a vpi object\
cumprod	- Cumulative product of elements\
cumsum	- Cumulative sum of elements\
factorial	- Computes the factorial of a large integer as a vpi\
nchoosek	- Binomial coefficient, nChoosek\
prod		- Product of elements\
sum		- Sum of elements\
\
\
Solutions to modular problems\
lineardiophantine - solve the linear Diophantine equation, A*x + B*y = C\
multiplicativeinverse - The multiplicative inverse of a: x such that (mod(a*x,p == 1)\
modroot	- Find x such that (mod(x^2,p) == a), the sqrt in modular arithmetic\
pell 		- Find nsol integer solution pairs to the pell equation x^2 - D*y^2 = 1\
\
\
Base conversion\
base2vpi	- Converts an integer in an arbitrary base into vpi (decimal) form\
bin2vpi	- Converts a binary representation of an integer into vpi (decimal) form\
double	- Conversion from a vpi object to a double\
single		- Conversion from a vpi object to a single.\
vpi2base	- Converts a vpi number to an arbitrary base (highest order "digit" first)\
vpi2bin	- Converts a vpi number to binary (highest order bit first)\
vpi2english	- Generate a readable text version of the number\
\
\
Other operations on or with a vpi object\
disp		- Disp a vpi object\
display	- Display a vpi object, calls disp\
randint	- Generate random integers from the set [1:n], uniform, with replacement\
vpi2english	- Generate a readable text version of the number\
\
\
As far as the general design of this toolbox, I chose to use the older style of having separate functions to create the class, since not yet enough people (in my opinion) have the most recent MATLAB release.\
\
I chose to optimize these tools, and especially the internal storage method, for speed of use. I might have chosen a different method that would use considerably less memory. For example, I store each digit separately as a double. This allows me to do many scalar multiplications and additions very efficiently. Had I chosen to store the digits each in a single int8 element, this would take much less memory, but the frequent problems with type changes would have made the risk of bugs higher, as well as making the code slow.\
\
In general, I'll invite you to have fun with these tools as I did in writing them. They are not an adequate substitute for those in the symbolic toolbox, but even after 20 years of working with the language I still find myself amazed at what you can do in MATLAB for only a few days of work invested.\
\
John D'Errico\
woodchips@rochester.rr.com\
1/26/09\
}